// https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<vector<int>> ans;

        if (n == 1) {
            ans.emplace_back(intervals[0]);
            return ans;
        }

        sort(intervals.begin(), intervals.end());

        int left = intervals[0][0];
        int right = intervals[0][1];

        for (int i = 1; i < n; i++) {
            int newLeft = intervals[i][0];
            int newRight = intervals[i][1];

            if (newLeft >= left && newLeft <= right) {
                right = max(right, newRight);
            } else {
                vector<int> inter;
                inter.emplace_back(left);
                inter.emplace_back(right);
                ans.emplace_back(inter);
                left = newLeft;
                right = newRight;
            }
        }

        vector<int> inter;
        inter.emplace_back(left);
        inter.emplace_back(right);
        ans.emplace_back(inter);

        return ans;
    }
};